{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Data Types and Operations on Data\n",
    "### PPL 2020 http://www.cs.bgu.ac.il/~ppl202\n",
    "\n",
    "In previous sections, we reviewed tools a programming language provides that help programmers design set of values that have common properties.  The concrete form is a type language with which we can express type annotations.  These type annotations denote sets of values.  They are associated to variables or function parameters and function return values. \n",
    "\n",
    "Such type annotations are useful to enable type checking - the process through which a compiler can ensure that variables will always be bound to values that belong to a specified type for all possible executions of the program - and issue errors when such assurance cannot be proven.\n",
    "Type annotations are also useful in documenting the intention of the programmer.\n",
    "\n",
    "Type definitions have a third important function: they help the programmer structure the code that operates on complex values in a way that reflects the structure of the data type.  \n",
    "In other words, knowing the structure of a data type helps the programmer write correct functions that operates over values of this type.  \n",
    "\n",
    "Reversely, programmers design and name types for sets of values that will be processed by the same set of functions. \n",
    "That is, type definitions allow the definition of uniform functional interfaces.\n",
    "\n",
    "We illustrate this point through 4 examples:\n",
    "* Homogeneous array types and the sequence interface (map, filter, reduce, ...)\n",
    "* Modeling trees\n",
    "* Mutable data types in FP\n",
    "* Disjoint types and Disjoint Unions to enable uniform functional interfaces"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Homogeneous Array Types and the Sequence Interface"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Array values can be homogeneous (all items have the same type) or heterogeneous (items of different types appear).\n",
    "\n",
    "The *natural* way to operate over arrays is to use the sequence interface - that is, a set of higher-order functions \n",
    "which can be applied on arrays.  For example:\n",
    "* `map(f, array)`\n",
    "* `filter(f, array)`\n",
    "* `reduce(f, array, init)`\n",
    "and similar functions (such as `every`, `some`, `find`).\n",
    "\n",
    "When we analyze the type of these functions, we realize that such operations will be easy and natural if the type of the function passed as a parameter is a simple type.  For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 1, 4, 9 ]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import {map} from 'ramda';\n",
    "{\n",
    "    let arr = [1,2,3];\n",
    "    map(x=>x*x, arr);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This operation over the array *works well* because the type of the mapper function is simple and can be derived from the type of the array:\n",
    "\n",
    "* `arr` is of type `number[]`\n",
    "* `x=>x*x` is a function of type `number=>number` - it can thus be applied to all the items in `arr`\n",
    "* the resulting array is also of type `number[]`\n",
    "\n",
    "Similarly, if we use a mapper function of type `number=>boolean` - we know the return value of `map` will be `boolean[]`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ false, false, true ]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import {map} from 'ramda';\n",
    "{\n",
    "    let arr = [1,2,3];\n",
    "    map(x=>x>2, arr);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Operating over a heterogeneous array like `[1,\"a\",true]` would make the usage of these functions much more challenging - because the mapper function would need to know what to do for each type of parameter.\n",
    "\n",
    "**Summary:** Homogeneous array types encourage the use of a simple functional interface - including map, filter, reduce.\n",
    "This functional interface (set of functions which operate on the same data structure) receive a function parameter with a simple type signature and abstract many forms of loops over repeated values of the same type."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Modeling Trees with Types"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us review the definition of a binary tree:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{ root: 1, left: { root: 2 }, right: { root: 3 } }"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "interface BinTree<T> {\n",
    "    root: T;\n",
    "    left?: BinTree<T>;\n",
    "    right?: BinTree<T>;\n",
    "}\n",
    "\n",
    "{\n",
    "    let bt2 : BinTree<number> = {\n",
    "        root:2,\n",
    "        left: {\n",
    "                root: 3,\n",
    "                left: { root: 4}\n",
    "        },\n",
    "        right: {\n",
    "                root: 5,\n",
    "                right: {root: 6}\n",
    "        }\n",
    "    };\n",
    "    \n",
    "    const square:(x:number) => number = x => x*x;\n",
    "    \n",
    "    const squareTree : (t: BinTree<number>) => BinTree<number> = (t) => {\n",
    "        if (t.left === undefined && t.right === undefined)\n",
    "            return {root: square(t.root)}\n",
    "        else if (t.left === undefined)\n",
    "            return {root: square(t.root), right: squareTree(t.right)};\n",
    "        else if (t.right === undefined)\n",
    "            return {root: square(t.root), left: squareTree(t.left)};\n",
    "        else\n",
    "            return {root: square(t.root), left: squareTree(t.left), right: squareTree(t.right)};\n",
    "    }\n",
    "    \n",
    "    squareTree(bt2);\n",
    "}\n",
    "\n",
    "const bt : BinTree<number> = {root: 1, left: {root: 2}, right: {root: 3}};\n",
    "bt;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When we write operations that operate over such trees, we must write code that operates according to the expected structure of the values in this type.\n",
    "\n",
    "For example, let us write a function that traverses a BinTree in Depth-First order:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "undefined"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{\n",
    "    const traverseDFS : <T>(t:BinTree<T>)=>void = (t) => {\n",
    "        console.log(t.root);\n",
    "        if (t.left !== undefined)\n",
    "            traverseDFS(t.left);\n",
    "        if (t.right !== undefined)\n",
    "            traverseDFS(t.right)\n",
    "    }\n",
    "    traverseDFS(bt);\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The structure of this function follows the structure of the type definition - when we process a value of type `BinTree`,\n",
    "we know that accessing the field `t.root` is safe (will not return `undefined` or throw an exception).\n",
    "To access `t.left` we must first check whether it is `undefined` since the type allows for this (base case of the recursion).\n",
    "If it is not, we know it must be a value of type `BinTree`.  \n",
    "\n",
    "In addition to these assurances, we also know that after checking these conditions we have checked all possible configurations of values (that is, the function exhaustively covers all possible `BinTree` values)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us consider a variant task where we actually build values of type `BinTree`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "{\n",
    "    let bt2 = {\n",
    "        root:2,\n",
    "        left: {\n",
    "           root: 3,\n",
    "           left: { root: 4}\n",
    "        },\n",
    "        right: {\n",
    "           root: 5,\n",
    "           right: {root: 6}\n",
    "        }\n",
    "    };\n",
    "    \n",
    "    const square:(x:number)=>number = x => x*x;\n",
    "    \n",
    "    const squareTree : (t: BinTree<number>) => BinTree<number> = (t) =>\n",
    "        (t.left === undefined && t.right === undefined) ?\n",
    "            {root: square(t.root)} \n",
    "        : (t.left === undefined) ?\n",
    "            {root: square(t.root), right: squareTree(t.right)}\n",
    "        : (t.right === undefined) ?\n",
    "            {root: square(t.root), left: squareTree(t.left)}\n",
    "        : {root: square(t.root), left: squareTree(t.left), right: squareTree(t.right)};\n",
    "    \n",
    "    squareTree(bt2);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function `squareTree` operates over a `BinTree` value and creates a new `BinTree` return value.\n",
    "It considers all possible configurations of `BinTree` (only root, root and left, root and right, root and left and right)\n",
    "and invokes the function `squareTree` recursively on each child value accordingly.\n",
    "\n",
    "In this case as well - type analysis allows us to verify that all accesses to the fields of the `BinTree` value are *safe*\n",
    "and that all recursive calls pass values of the right type as parameters.  In addition, we can verify that the function\n",
    "is *exhaustive* in checking all possible configurations for the value.\n",
    "\n",
    "We can *relax* the type checking - and accept to receive values of type `undefined` in addition - yielding slightly shorter and more readable code, as shown below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{ root: 4,\n",
       "  left: \n",
       "   { root: 9,\n",
       "     left: { root: 16, left: undefined, right: undefined },\n",
       "     right: undefined },\n",
       "  right: \n",
       "   { root: 25,\n",
       "     left: undefined,\n",
       "     right: { root: 36, left: undefined, right: undefined } } }"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{\n",
    "    let bt3 = {\n",
    "        root:2,\n",
    "        left: {\n",
    "                root: 3,\n",
    "                left: { root: 4}\n",
    "        },\n",
    "        right: {\n",
    "                root: 5,\n",
    "                right: {root: 6}\n",
    "        }\n",
    "    };\n",
    "    const square:(x:number)=>number = x => x*x;\n",
    "    const squareTree2 : (t: BinTree<number> | undefined) => (BinTree<number> | undefined) = (t) =>\n",
    "        (t === undefined) ? undefined\n",
    "        : {\n",
    "            root: square(t.root),\n",
    "            left: squareTree2(t.left),\n",
    "            right: squareTree2(t.right)\n",
    "        };\n",
    "    squareTree2(bt3);\n",
    "}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Observe that in this version:\n",
    "* We extended the expected values of type `BinTree` to also include the value `undefined`.\n",
    "* We explicitly test for this value as the first base case in the recursive function `squareTree2`.\n",
    "* The recursive calls are now simplified as we don't need to avoid the recursive calls with a value `undefined`\n",
    "* The return value has values marked explicitly as `undefined` - these are semantically equivalent to *absent* values - but in the syntax of the object, they still appear.\n",
    "\n",
    "We can get rid of them using a simple idiom:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{ root: 4,\n",
       "  left: { root: 9, left: { root: 16 } },\n",
       "  right: { root: 25, right: { root: 36 } } }"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "JSON.parse(JSON.stringify({ root: 4,\n",
    "  left: \n",
    "   { root: 9,\n",
    "     left: { root: 16, left: undefined, right: undefined },\n",
    "     right: undefined },\n",
    "  right: \n",
    "   { root: 25,\n",
    "     left: undefined,\n",
    "     right: { root: 36, left: undefined, right: undefined } } }));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The difference between the two versions is a matter of style preference.\n",
    "In general, the presence of `undefined` values complicates type analysis, but it is difficult to avoid dealing with it explicitly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## *Mutable* (Persistent) Data Types in FP\n",
    "\n",
    "We indicated earlier that FP encourages immutable variables and data structures to achieve the goals of determinism (calling the same function with the same arguments should return the same value) and safe concurrency (avoid shared mutable data across threads). \n",
    "\n",
    "Yet, some data types are thought of a **mutable** in their definition.  Consider the example of a **stack**.  It is defined as a container of values that enforces a specific access pattern through an interface:\n",
    "* `push(x)`: modifies the stack by adding a new value x on top of it.\n",
    "* `pop()`: modifies the stack by removing the top value of the stack and returning its value.\n",
    "* `empty()`: determines whether the stack is empty.\n",
    "\n",
    "As was discussed in SPL (https://www.cs.bgu.ac.il/~spl201 for those who took this course), in OOP, it is useful to split the Stack interface into **Queries** (functions that only return information about the data structure without changing it) and **Commands** (functions which only modify the data structure and do not return any value). Such distinction makes writing tests much easier.\n",
    "\n",
    "To adopt this distinction, we split the `pop()` method into two distinct methods:\n",
    "* `peek()`: returns the value of the top element in the stack (this is a query method).\n",
    "* `pop()`: modifies the stack by removing the top element (this is a command method - that just has a side effect and no return value).\n",
    "\n",
    "This definition is inherently procedural - as it defines the data type in terms of mutation (with the commands `push()` and `pop()`) in addition to the queries `peek()` and `empty()`.\n",
    "\n",
    "Note that according to this methodology, even the queries are **not** pure functions - because they are not deterministic (that is, we can call the same function twice on the same variable at different times and obtain different answers).\n",
    "Let us illustrate these points with a simple implementation of Stacks in TypeScript:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 0, 1, 2, 3 ]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// Mutable implementation of stacks (NON Functional)\n",
    "\n",
    "// Constructor\n",
    "const makeStack = <T>(initValues: T[]):T[] => initValues;\n",
    "\n",
    "// peek and empty are queries - they do not mutate the stack\n",
    "const peek = <T>(stack:T[]):T => stack[0];\n",
    "const empty = <T>(stack:T[]):boolean => stack.length === 0;\n",
    "\n",
    "// push() and pop() are commands - they mutate the stack and return void (no return value) \n",
    "const push = <T>(stack:T[], newVal:T):void => {stack.unshift(newVal); return;}\n",
    "const pop = <T>(stack:T[]):void => {stack.shift(); return;}\n",
    "\n",
    "{\n",
    "    let s = makeStack([1,2,3])\n",
    "    push(s, 0);\n",
    "    s;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This implementation relies on an array encoding for Stack values.\n",
    "It relies on generic data types in TypeScript so that we can use it for Stacks of any type - as long as it is a homogeneous stack.\n",
    "\n",
    "It relies on the fact that arrays in JavaScript are mutable - and implements `push()` using the primitive `unshift()` operation on arrays, and `pop()` using the primitive `shift()` operation.\n",
    "\n",
    "We skipped checking the preconditions to simplify the presentation.\n",
    "\n",
    "Note the specific style: commands (functions that have a side-effect - in this case `push()` and `pop()`) have no return value - we mark them as `void` in TypeScript.  \n",
    "\n",
    "In contrast, queries (functions that have no side-effect and only return information about the data structure - in this case `peek()` and `empty()`) return a value.\n",
    "\n",
    "Given that the underlying data type is mutable, we cannot obtain deterministic behavior:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "undefined"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{\n",
    "    let s = makeStack([1,2,3])\n",
    "    push(s, 0);\n",
    "    console.log(peek(s));\n",
    "    pop(s);\n",
    "    console.log(peek(s));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The same operation `peek(s)` on the same variable `s` returns different values when mutation has occurred between the two calls.\n",
    "This is a case of *non-determinism* due to mutation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Functional Stack: Step 1\n",
    "\n",
    "Can we define a **functional data structure** for the Stack data type?\n",
    "\n",
    "For example, can we define a Stack data structure that operates as an immutable data structure, while still offering the same interface to its clients (`peek`, `empty`, `push`, `pop`)?\n",
    "\n",
    "The key change that is required to obtain such immutable functional data types is to modify the **commands** so that instead of mutating the existing data structure and returning `void` (that is, having no return value), the commands will return a new copy of the data structure.\n",
    "\n",
    "This imposes first a change on the type of the functions, next a change on the client side.  Let us illustrate this first round of changes (which we will find out is necessary but not sufficient):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 0, 1, 2, 3 ]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// Implementation 2 of stacks (Towards Functional - not yet)\n",
    "\n",
    "// To document the type, we give it a name - distinct from its implementation.\n",
    "type Stack<T> = T[];\n",
    "\n",
    "// Constructor\n",
    "const makeStack = <T>(initValues: T[]):Stack<T> => initValues;\n",
    "\n",
    "// peek and empty are queries - they do not mutate the stack - no change needed from V1 above.\n",
    "const peek = <T>(stack:Stack<T>):T => stack[0];\n",
    "const empty = <T>(stack:Stack<T>):boolean => stack.length === 0;\n",
    "\n",
    "// push() and pop() are commands - they return a new version of the stack (instead of void in V1)\n",
    "const push = <T>(stack:Stack<T>, newVal:T):Stack<T> => {stack.unshift(newVal); return stack;}\n",
    "const pop = <T>(stack:Stack<T>):Stack<T> => {stack.shift(); return stack;}\n",
    "\n",
    "{\n",
    "  let s1 = makeStack([1,2,3]),\n",
    "      s2 = push(s1, 0); // This is a new stack\n",
    "    s2;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This modification in the signature of the commands requires clients to change as well: each time a command is invoked, we must bind the return value to a new variable so that it can be used further:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{\n",
    "  let s1 = makeStack([1,2,3]);\n",
    "  {\n",
    "    let s2 = push(s1, 0); // This is a new stack\n",
    "    console.log(peek(s2));\n",
    "    {\n",
    "      let s3 = pop(s2);   // Another stack\n",
    "      peek(s3);\n",
    "    }\n",
    "  }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Value Aliasing\n",
    "\n",
    "In this new style, we do not observe direct mutation - the calls seem to be deterministic.\n",
    "\n",
    "**Unfortunately, this is an illusion:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "const s1 = makeStack([1,2,3]);\n",
    "const s2 = push(s1,0);\n",
    "const s3 = pop(s2);\n",
    "peek(s1);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 2, 3 ]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pop(s1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "peek(s1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The implementation relies on JavaScript arrays - which are internally mutable. \n",
    "We did not prevent this mutation by just changing the signature of the methods, because in the body of the commands we still call mutators on the internal representation of the stack.\n",
    "\n",
    "The situation is even worse because we have created a very risky situation called **variable aliasing** - the stacks `s2` and `s3` share in memory cells that are used by `s1`.  As a result, operations on `s1` end up modifying the state of `s2`.\n",
    "If we now call the same expression `peek(s2)` and `peek(s3)` - we obtain different values from the earlier results (0 and 1) **even though no direct mutation of `s2` and `s3` was performed**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "peek(s2) // This was 0 before invoking pop(s1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "peek(s3) // This was 1 before invoking pop(s1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The reason the stacks `s2` and `s3` were changed when we applied mutation on `s1` is because the 3 stacks actually share parts of their value in memory - because Arrays in JavaScript behave like pointers to values in C++."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Functional Stack: Step 2\n",
    "\n",
    "The solution to this problem is to require that commands actually **copy** the data structure when they need to modify it - so that each returned value is indeed a new value - and not an **alias** of the previous value.\n",
    "\n",
    "This can be achieved by this new version of the Stack code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 0, 1, 2, 3 ]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// Implementation 3 of stacks (Functional - but inefficient)\n",
    "\n",
    "// To document the type, we give it a name - distinct from its implementation.\n",
    "type Stack<T> = T[];\n",
    "\n",
    "// A utility to clone an array - relies on the fact that concat copies\n",
    "// This is a shallow copy\n",
    "const cloneArray = <T>(array: T[]):T[] => [].concat(array);\n",
    "\n",
    "// Constructor\n",
    "const makeStack = <T>(initValues: T[]):Stack<T> => cloneArray(initValues);\n",
    "\n",
    "// peek and empty are queries - they do not mutate the stack - no change needed from V1.\n",
    "const peek = <T>(stack:Stack<T>):T => stack[0];\n",
    "const empty = <T>(stack:Stack<T>):boolean => stack.length === 0;\n",
    "\n",
    "// push() and pop() are commands - they return a new copy of the stack \n",
    "const push = <T>(stack:Stack<T>, newVal:T):Stack<T> => {\n",
    "    let res = cloneArray(stack);\n",
    "      res.unshift(newVal); \n",
    "      return res;\n",
    "}\n",
    "const pop = <T>(stack:Stack<T>):Stack<T> => {\n",
    "    let res = cloneArray(stack);\n",
    "      res.shift(); \n",
    "      return res;\n",
    "}\n",
    "\n",
    "{\n",
    "  let s1 = makeStack([1,2,3]),\n",
    "      s2 = push(s1, 0); // This is a new stack\n",
    "    s2;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us verify that this new implementation provides deterministic behavior for the Stack functions and no aliasing:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "1\n",
      "0\n",
      "1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "undefined"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{\n",
    "    let s1 = makeStack([1,2,3]),\n",
    "        s2 = push(s1, 0); // This is a new stack\n",
    "    console.log(peek(s2)); // Should be 0\n",
    "    {\n",
    "        let s3 = pop(s2);   // Another stack\n",
    "        console.log(peek(s3)); // Should be 1\n",
    "        // Let's now change s1 and \n",
    "        // verify s2 and s3 are not affected\n",
    "        pop(s1);\n",
    "        console.log(peek(s1));   // Should remain 1\n",
    "        console.log(peek(s2));   // Should remain 0\n",
    "        console.log(peek(s3));   // Should remain 1\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This implementation is **safe** - it does not introduce unexepected side effects to the data structures, and the data structures remain immutable.  \n",
    "\n",
    "The cost of this implementation, though, is that each mutation requires a full copy of the data structure.\n",
    "This is inefficient in RAM (we obtain many copies of the same objects) and in CPU (the copying operations are expensive)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Efficient Functional Data Structures: Step 3\n",
    "\n",
    "Based on the technique of **amortization**, the work of Okasaki has demonstrated how one can design **efficient functional data structures** that are immutable and still avoid unnecessary copying.\n",
    "\n",
    "The book: *Purely Functional Data Structures* Chris Okasaki, Cambridge University Press, 1999 presents this general\n",
    "approach.  It has become the standard reference to design efficient data structures for FP.  In particular, it has been \n",
    "the basis for the design of the Clojure programming language.\n",
    "\n",
    "Recently, the library **Immutable** https://facebook.github.io/immutable-js/ has been developed in TypeScript by Facebook.\n",
    "It provides an efficient immutable implementation of the main collection data structures (Map, Stack, Queue, Lists, Set)\n",
    "based on Okasaki's original description. (If you haven't installed `immutable` - run the command:\n",
    "```\n",
    "$ npm install immutable --save\n",
    "```\n",
    "in a shell window.\n",
    "\n",
    "Using the Immutable Stack implementation is performed as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "s1.size = 3\n",
      "s2.size = 4\n",
      "s1.peek() = 1\n",
      "s2.peek() = 0\n",
      "After performing s1.pop() and s2.pop()\n",
      "s1.size = 3\n",
      "s2.size = 4\n",
      "s3.size = 2\n",
      "s4.size = 3\n",
      "s1.peek() = 1\n",
      "s2.peek() = 0\n",
      "s3.peek() = 2\n",
      "s4.peek() = 1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "undefined"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import { Stack as iStack } from 'Immutable';\n",
    "\n",
    "let s1 = iStack.of(1,2,3),\n",
    "    s2 = s1.push(0);\n",
    "    console.log(`s1.size = ${s1.size}`);\n",
    "    console.log(`s2.size = ${s2.size}`);\n",
    "    console.log(`s1.peek() = ${s1.peek()}`);\n",
    "    console.log(`s2.peek() = ${s2.peek()}`);\n",
    "    let s3 = s1.pop(),\n",
    "        s4 = s2.pop();\n",
    "        console.log('After performing s1.pop() and s2.pop()')\n",
    "        console.log(`s1.size = ${s1.size}`);\n",
    "        console.log(`s2.size = ${s2.size}`);\n",
    "        console.log(`s3.size = ${s3.size}`);\n",
    "        console.log(`s4.size = ${s4.size}`);\n",
    "        console.log(`s1.peek() = ${s1.peek()}`);\n",
    "        console.log(`s2.peek() = ${s2.peek()}`);\n",
    "        console.log(`s3.peek() = ${s3.peek()}`);\n",
    "        console.log(`s4.peek() = ${s4.peek()}`);\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We confirm that the Stack functions behave in a deterministic manner, with no aliasing. Yet, internally, minimal copying was performed.\n",
    "\n",
    "Immutable works well with JSON and encourages the usage of embedded data structures in a safe immutable and efficient manner.\n",
    "It thus provides an essential component of FP in Typescript."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'[1,2,3]'"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "JSON.stringify(s1);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{ name: 'avi', age: 23 }"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import { Stack  as iStack } from 'Immutable'\n",
    "let personsStack = iStack(JSON.parse('[{\"name\":\"avi\", \"age\":23}, {\"name\":\"bob\", \"age\":26}]'));\n",
    "    personsStack.peek();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Disjoint Types and Disjoint Union\n",
    "\n",
    "We have highlighted the perspective of Data Types as denoting sets of values over which common operations can be performed.\n",
    "On the basis of this understanding, we defined operations over types which correspond to Set operations - such as Union and Intersection.  \n",
    "\n",
    "Such operations are provided for example in TypeScript, and we can define types such as:\n",
    "\n",
    "```\n",
    "type NoS = number | string;   // union: values that are either numbers or strings\n",
    "type SoB = string | boolean;  // union: either string or boolean\n",
    "type S = NoS & SoB;           // intersection - should be back to string.\n",
    "```\n",
    "\n",
    "We have also defined that the type system implemented in Typescript follows **structural subtyping** as opposed to\n",
    "**nominal subtyping**.  For example, if we define two types:\n",
    "\n",
    "```\n",
    "interface Person { name: string; address: string};    // a person record in a Database\n",
    "interface Variable { name: string; address: string};  // a variable declaration in an Interpreter\n",
    "\n",
    "let p:Person = {name:\"a\", address:\"2\"},\n",
    "    v:Variable = p; // Compiles ok\n",
    "```\n",
    "\n",
    "Under **nominal typing** (like it exists in Java for example), these two types would be disjoint - values of type Person and values of type Variable would be different.\n",
    "\n",
    "Under **structural typing** (like it exists in Typescript), these two types are actually equal - they describe the same set of values.\n",
    "\n",
    "When modeling data types, we are often interested in distinguishing such types - so that the values we describe are distinct,\n",
    "and we cannot confuse a Person value with a Variable value.\n",
    "\n",
    "The way to obtain this behavior is to add a discriminant field - called a **tag** - to distinguish values that are intended of being of different types."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{ tag: 'person', name: 'a', address: '2' }"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "const PERSON = \"person\";\n",
    "const VARIABLE = \"variable\";\n",
    "\n",
    "interface Person { \n",
    "    tag: typeof PERSON;\n",
    "    name: string; \n",
    "    address: string\n",
    "};    // a person record in a Database\n",
    "interface Variable { \n",
    "    tag: typeof VARIABLE;\n",
    "    name: string; \n",
    "    address: string\n",
    "};  // a variable declaration in an Interpreter\n",
    "\n",
    "{\n",
    "  let p:Person = {tag: PERSON, name:\"a\", address:\"2\"},\n",
    "      v:Variable = p; // Does NOT compile:\n",
    "      // message: 'Type 'Person' is not assignable to type 'Variable'.\n",
    "      // Types of property 'tag' are incompatible.\n",
    "    p;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this example, the type of the `tag` field is a set of a single value - the string \"person\" or the string \"variable\".\n",
    "\n",
    "With the addition of the `tag` field with these specifications, the two types `Person` and `Variable` have become **disjoint** - that is, the set of values these type annotations denote are disjoint."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Disjoint Union\n",
    "\n",
    "The possibility to define disjoint types can be combined into a very common pattern called **disjoint union**.\n",
    "\n",
    "In set theory, the **disjoint union of two sets** $A$ and $B$ (https://en.wikipedia.org/wiki/Disjoint_union) is \n",
    "is a binary operator that combines all distinct elements of a pair of given sets, while retaining the original \n",
    "set membership as a distinguishing characteristic of the union set.\n",
    "\n",
    "$A \\cup^+ B = (A \\times \\{0\\}) \\cup (B \\times \\{1\\})$\n",
    "\n",
    "For example:\n",
    "\n",
    "$\\{0,1,2\\} \\cup^+ \\{2,3\\} = \\{ (0,0), (1,0), (2,0), (2,1), (3,1) \\}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We identify in that operation that the elements (0, 1) added to each pair play a role similar to the `tag` field we added to map types to make them disjoint.\n",
    "\n",
    "In type descriptions, in order to define a **disjoint union type**, we define the union of two (or more) map types which are made disjoint by using the same `tag` field. \n",
    "\n",
    "**NOTE**: `tag` is just a key, any other key could be used - for example, `type` or `kind` are often used.  The key must be used consistently across all the types that appear in the union.\n",
    "\n",
    "For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "undefined"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type Shape = Circle | Rectangle | Triangle;\n",
    "\n",
    "interface Circle {\n",
    "    tag: \"circle\";\n",
    "    center: {x:number, y:number};\n",
    "    radius: number;\n",
    "}\n",
    "\n",
    "interface Rectangle {\n",
    "    tag: \"rectangle\";\n",
    "    upperLeft: {x:number, y:number};\n",
    "    lowerRight: {x:number; y:number};\n",
    "}\n",
    "\n",
    "interface Triangle {\n",
    "    tag: \"triangle\";\n",
    "    p1: {x:number, y:number};\n",
    "    p2: {x:number, y:number};\n",
    "    p3: {x:number, y:number};\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These type definitions allow this type of processing - which is \"case by case\" processing of all the options in the disjoint union:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12.56"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "const area = (s:Shape):number => {\n",
    "    switch(s.tag) {\n",
    "        case \"circle\": return s.radius * s.radius *  3.14;\n",
    "        case \"rectangle\": return (s.upperLeft.x - s.lowerRight.x) * (s.upperLeft.y - s.lowerRight.y);\n",
    "        case \"triangle\": return 0; // I do not know the formula :(\n",
    "    }\n",
    "}\n",
    "\n",
    "area({tag:\"circle\", center:{x:0,y:0}, radius:2})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The tool of disjoint union together with the corresponding `switch` construct achieves an effect similar to sub-classes with virtual classes in Object-Oriented Programming.  It allows the function to dispatch to different computations based on the type of the actual value received as a parameter.\n",
    "\n",
    "The definition of the Union type in this specific context makes sense because it expresses the intention of the programmer:\n",
    "* these are disjoint types - they have no commonality in structure\n",
    "* but they have a similar functional interface - we *consume* them in a similar manner.\n",
    "\n",
    "Note that the type checker can determine that the switch construct covers all possible options - based on the structure of the type union - and for each case, it can check the expected keys based on the value of the tag key."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Summary\n",
    "\n",
    "* Type definitions help the programmer structure the code that operates on complex values in a way that reflects the structure of the data type.\n",
    "* Programmers design and name types for sets of values that will be processed by the same set of functions.\n",
    "\n",
    "* Homogeneous array types encourage the programmer to consume them using the sequence interface (map, filter, reduce) with processing functions applied to each item of the same type.\n",
    "* Recursive types are processed by recursive functions which inspect the values accordig to the type definition - and can determine the base case and the inductive case.  We illustrated this with Tree processing functions.\n",
    "* Mutable data types can be modelled in a Functional Programming style by making sure *commands* are written as *constructors* which return a new version of the values, instead of mutating an existing value.  We illustrated this on the case of the **stack** data type.\n",
    "* Disjoint types and Disjoint Unions enable the definition of uniform functional interfaces over types of values that are not structurally similar."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Typescript 2.9",
   "language": "typescript",
   "name": "typescript"
  },
  "language_info": {
   "file_extension": ".ts",
   "mimetype": "text/x-typescript",
   "name": "typescript",
   "version": "2.9.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}